#include<stdio.h>
#include<assert.h>
#include<malloc.h>
#include"dsqlist.h"

//要干的事情

//初始化
//判满
//判空
//插入数据，在ps顺序表的pos位置插入val;
//在ps中查找第一个key值，找到返回下标，没有找到返回-1；
//删除pos位置的值
//删除第一个val的值
//返回key的前驱下标，如果不存在返回-1；
//返回key的后继下标，如果不存在返回-1；
//输出
//清空数据
//销毁整个内存



//初始化：

//初始化要干的事情：
//1.动态创建长度为10的数组
//2.有效长度为0
//3.总容量位10


//C语言中：数组或者结构体作为形参传递时一定传的是指针
// 1.传指针可以节省内存
// 2.传指针可以修改实参

//补：C++中传递的是引用


void InitSqlist(DPSQList ps)
{
	assert(ps != NULL);
	if (ps == NULL)
		return;

	ps->elem = (int*)malloc(INIT_SIZE * sizeof(int));
	ps->length = 0;
	ps->listsize = INIT_SIZE;
}


//判满
//若有效数据个数 ==总容量相等就是满的
static bool IsFull(DPSQList ps)
{
	return ps->length == ps->listsize;
}


//扩容

//一般来说，扩容两倍
static bool Inc(DPSQList ps)
{
	assert(ps != NULL);
	if (ps == NULL)
		return false;

	ps->elem = (int*)realloc(ps->elem, ps->listsize * 2 * sizeof(int));
	assert(ps->elem != NULL);
	ps->listsize *= 2;
	//ps->length;
	return true;
}

//插入数据，在ps顺序表的pos位置插入val;
bool Insert(DPSQList ps, int pos, int val)
{
	//参数判断
	assert(ps != NULL);
	if (ps == NULL)
		return false;

	//边界问题
	if (pos<0 || pos>ps->length)
	{
		return false;
	}
	//若满了，则要扩容
	if (IsFull(ps))
	{
		Inc(ps);
	}

	//把数据往后移
	for (int i = ps->length - 1; i >= pos; i--)
	{
		ps->elem[i + 1] = ps->elem[i];
	}
	//插入新数据
	ps->elem[pos] = val;
	//有效数据个数++
	ps->length++;

	return true;
}
//判空
bool IsEmpty(DPSQList ps)
{
	assert(ps != NULL);
	if (ps == NULL)
		return false;
	return ps->length == 0;
}

//在ps中查找第一个key值，找到返回下标，没有找到返回-1；
int Search(DPSQList ps, int key)
{
	assert(ps != NULL);
	if (ps == NULL)
		return -1;
	//遍历一遍
	for (int i = 0; i < ps->length; i++)
	{
		if (key == ps->elem[i])
			return i;
	}
	return -1;
}

//删除pos位置的值
bool DelPos(DPSQList ps, int pos)
{
	assert(ps != NULL);
	if (ps == NULL)
		return false;

	if (pos < 0 || pos >= ps->length)
	{
		return false;
	}
	//后面的数据前移
	for (int i = pos; i < ps->length - 1; i++)
	{
		ps->elem[i] = ps->elem[i + 1];
	}
	//有效数据--；
	ps->length--;
	return true;
}

//删除第一个val的值
bool DelVal(DPSQList ps, int val)
{
	assert(ps != NULL);
	if (ps == NULL)
		return false;
	int i = Search(ps, val);
	if (i < 0)
		return false;

	return DelPos(ps, i);
}

//返回key的前驱下标，如果不存在返回-1；
int GetPrio(DPSQList ps, int key)
{
	assert(ps != NULL);
	if (ps == NULL)
		return -1;
	int i = Search(ps, key);
	if (i <= 0)
		return -1;

	return i - 1;
}

//返回key的后继下标，如果不存在返回-1；
int GetNext(DPSQList ps, int key)
{
	assert(ps != NULL);
	if (ps == NULL)
		return -1;
	int i = Search(ps, key);
	if (i < 0 || i == ps->length - 1)
		return -1;

	return i + 1;
}

//输出
void Show(DPSQList ps)
{
	assert(ps != NULL);
	if (ps == NULL)
		return;
	for (int i = 0; i < ps->length; i++)
	{
		printf("%d  ", ps->elem[i]);
	}
	printf("\n");
}

//清空数据
void Clear(DPSQList ps)
{
	ps->length = 0;
}

//销毁整个内存

//1.释放动态内存，否则内存泄漏
//2.有效数据个数为0
//3.总容量为0

void Destroy(DPSQList ps)
{
	free(ps->elem);
	ps->elem = NULL;
	ps->length = 0;
	ps->listsize = 0;
	ps = NULL;//无效的代码
}


bool Compare(DPSQList ps1, DPSQList ps2)
{
	for (int i = 0, j = 0;i < ps1->length, j < ps2->length;i++, j++)
	{
		if (ps1->elem[i] == ps2->elem[j])
		{
			return true;
		}
		return false;
	}
}


void Reverse(DPSQList ps)
{
	int i = 0;
	int j = INIT_SIZE;
	int tmp = 0;
	while (i < j)
	{
		tmp = ps->elem[i];
		ps->elem[i]=ps->elem[j];
		ps->elem[j] = tmp;
		i++;
		j--;
	}
}


